#
# @lc app=leetcode.cn id=144 lang=python3
#
# [144] 二叉树的前序遍历
#
from typing import List
from queue import LifoQueue, Queue


# @lc code=start
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def recursion(self, tree, ans):
        ans.append(tree.val)
        tree.left and self.recursion(tree.left, ans)
        tree.right and self.recursion(tree.right, ans)

    def preorderTraversal1(self, root: TreeNode) -> List[int]:
        if not root:
            return []

        ans = []

        def recursion(tree, ans):
            ans.append(tree.val)
            tree.left and recursion(tree.left, ans)
            tree.right and recursion(tree.right, ans)

        recursion(root, ans)

        return ans

    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []

        q = LifoQueue()
        q.put(root)
        ans = []
        while not q.empty():
            node = q.get()
            ans.append(node.val)
            node.right and q.put(node.right)
            node.left and q.put(node.left)

        return ans


def mkTreeNode(lst):
    if len(lst) == 0:
        return None

    q = Queue()
    head = TreeNode(lst[0])
    q.put(head)

    i = 1
    l = len(lst)
    while i < l:
        node = q.get()
        if lst[i]:
            left = TreeNode(lst[i])
            node.left = left
            q.put(left)
        i += 1
        if i < l and lst[i]:
            right = TreeNode(lst[i])
            node.right = right
            q.put(right)
        i += 1

    return head


if __name__ == "__main__":
    s = Solution()
    print(s.preorderTraversal(mkTreeNode([1, None, 2, 3])), [1, 2, 3])
    print(s.preorderTraversal(mkTreeNode([1, 2, None, 3])), [1, 2, 3])
    print(s.preorderTraversal(mkTreeNode([])), [])
    print(s.preorderTraversal(mkTreeNode([1, 4, 3, 2])), [1, 4, 2, 3])
# @lc code=end
